# https://leetcode-cn.com/problems/find-in-mountain-array/

class MountainArray:
   def get(self, index: int) -> int: pass
   def length(self) -> int: pass


class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        left , right = 0, MountainArray.length(mountain_arr) - 1
        # 1. 首先计算中间值，山峰顶部的元素位置
        mid = 0
        while left < right:
            mid = left + (right - left) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        mid = left
        print(mid)

        # 2. 定义一个二分查找的方法
        def getLeftPos(left, right, target):
            print(22)
            while left <= right:
                mid = left + (right - left) // 2
                temp = mountain_arr.get(mid)
                if temp == target:
                    return mid
                elif temp < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return -1

        def getRightPos(left, right, target):
            '''
            while left <= right:
                mid = left + (right - left) // 2
                print(left, right, mid)
                temp = mountain_arr.get(mid)
                if temp == target:
                    return mid
                elif temp > target:
                    left = mid + 1
                else:
                    right = mid - 1
# 0 1 2 4 2 1
            return -1
            '''
            while left < right:
                mid = left + (right - left + 1) // 2 
                temp = mountain_arr.get(mid)
                print(left, right, mid)
                if temp >= target:
                    left = mid
                else:
                    right = mid - 1
             
            return left if mountain_arr.get(left) == target else -1

        index = getLeftPos(0, mid, target)
        
        return index if index >= 0 else getRightPos(mid + 1, mountain_arr.length()-1, target)

